package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-08-25
 **/

public class No797所有可能的路径 {

    /**
     * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
     * 二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
     * 译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
     *
     * 示例 1：
     * 输入：graph = [[1,2],[3],[3],[]]
     * 输出：[[0,1,3],[0,2,3]]
     * 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
     * 示例 2：
     * 输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
     * 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
     * 示例 3：
     * 输入：graph = [[1],[]]
     * 输出：[[0,1]]
     * 示例 4：
     * 输入：graph = [[1,2,3],[2],[3],[]]
     * 输出：[[0,1,2,3],[0,2,3],[0,3]]
     * 示例 5：
     * 输入：graph = [[1,3],[2],[3],[]]
     * 输出：[[0,1,2,3],[0,3]]
     *  
     *
     * 提示：
     * n == graph.length
     * 2 <= n <= 15
     * 0 <= graph[i][j] < n
     * graph[i][j] != i（即，不存在自环）
     * graph[i] 中的所有元素 互不相同
     * 保证输入为 有向无环图（DAG）
     */

    private int[][] graph;
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph = graph;
        Deque<Integer> path = new ArrayDeque<>();
        path.add(0);
        this.dfs(0, path, new HashSet<>());
        return result;
    }

    private void dfs(int thinNum, Deque<Integer> path, Set<Integer> setPath) {

        if (thinNum == graph.length - 1) {
            result.add(new ArrayList<>(path));
            return;
        }


        int[] arr = graph[thinNum];
        for (int num : arr) {

            if (setPath.contains(num)) {
                continue;
            }

            path.addLast(num);
            setPath.add(num);
            dfs(num,path,setPath);
            path.removeLast();
            setPath.remove(num);
        }

    }

    public static void main(String[] args) {
        No797所有可能的路径 n = new No797所有可能的路径();
        int[][] arr = {{4,3,1},{3,2,4},{3},{4},{}};
        List<List<Integer>> result = n.allPathsSourceTarget(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
